package gold.digger;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LCJZOF51 {
    public long startExecuteTime = System.currentTimeMillis();


    public class Solution {
        public int reversePairs(int[] nums) {
            int len = nums.length;

            if (len < 2) {
                return 0;
            }

            int[] copy = new int[len];
            for (int i = 0; i < len; i++) {
                copy[i] = nums[i];
            }

            int[] temp = new int[len];
            return reversePairs(copy, 0, len - 1, temp);
        }

        private int reversePairs(int[] nums, int left, int right, int[] temp) {
            if (left == right) {
                return 0;
            }

            int mid = left + (right - left) / 2;
            int leftPairs = reversePairs(nums, left, mid, temp);
            int rightPairs = reversePairs(nums, mid + 1, right, temp);

            if (nums[mid] <= nums[mid + 1]) {
                return leftPairs + rightPairs;
            }

            int crossPairs = mergeAndCount(nums, left, mid, right, temp);
            return leftPairs + rightPairs + crossPairs;
        }

        private int mergeAndCount(int[] nums, int left, int mid, int right, int[] temp) {
            for (int i = left; i <= right; i++) {
                temp[i] = nums[i];
            }

            int i = left;
            int j = mid + 1;

            int count = 0;
            for (int k = left; k <= right; k++) {

                if (i == mid + 1) {
                    nums[k] = temp[j];
                    j++;
                } else if (j == right + 1) {
                    nums[k] = temp[i];
                    i++;
                } else if (temp[i] <= temp[j]) {
                    nums[k] = temp[i];
                    i++;
                } else {
                    nums[k] = temp[j];
                    j++;
                    count += (mid - i + 1);
                }
            }
            return count;
        }
    }


    class Solution_Time_Exceed {
        public int reversePairs(int[] nums) {
            int[] sorted = new int[nums.length];
            Arrays.fill(sorted, Integer.MIN_VALUE);

            int ans = 0, endPos = 0;
            for (int num : nums) {
                ans += insert(sorted, endPos++, num);
            }

            return ans;
        }

        public int insert(int[] sorted, int endPos, int val) {
            if (endPos == 0) {
                sorted[0] = val;
                return 0;
            }

            int left = 0, right = endPos - 1;
            while (left < right - 1) {
                int mid = left + (right - left) / 2;// posMid-1 <= val < posMid
                if (val >= sorted[mid]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }

            if (val < sorted[0]) {
                for (int i = endPos; i >= 1; i--) {
                    sorted[i] = sorted[i - 1];
                }
                sorted[0] = val;
                return endPos;
            }

            for (int i = Math.max(1, left - 1); i <= endPos; i++) {
                if (val < sorted[i]) {
                    for (int j = endPos; j > i; j--) {
                        sorted[j] = sorted[j - 1];
                    }
                    sorted[i] = val;
                    return endPos - i;
                }
                if (i == endPos) {
                    sorted[endPos] = val;
                    return 0;
                }
            }

            return 0;
        }
    }

    public void run() {
        int[] arr = new int[100];
        Arrays.fill(arr, Integer.MIN_VALUE);
        System.out.println(new Solution_Time_Exceed().insert(arr, 0, 7));
        System.out.println(new Solution_Time_Exceed().insert(arr, 1, 5));
        System.out.println(new Solution_Time_Exceed().insert(arr, 2, 6));
        System.out.println(new Solution_Time_Exceed().insert(arr, 3, 4));
        System.out.println(new Solution().reversePairs(InputUtil.toIntegerArray("[7,5,6,4]")));
    }

    public static void main(String[] args) throws Exception {
        LCJZOF51 an = new LCJZOF51();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
